package Midium;

import java.util.Arrays;

// 1749. 任意子数组和的绝对值的最大值
/*
 * 题目：
 * 给你一个整数数组nums。
 * 一个子数组[numsl, numsl+1, ..., numsr-1, numsr]的和的绝对值为
 * abs(numsl + numsl+1 + ... + numsr-1 + numsr)。
 * 请你找出 nums中和的绝对值最大的任意子数组（可能为空），并返回该最大值。
 * --------------------------------------------------------
 * 我的思路（错误！）：
 * 贪心，每次加上一个数以后，和当前数比较，如果加上这个数，还不如从这个数开始，那就从这个数开始
 * 同时，更新max，即.如果curSum不断减去当前子数组的第一个元素后，能变得更大，就变大
 * --------------------------------------------------------
 * 我的思路错误在于，没有考虑到负数参与变化的情况
 * --------------------------------------------------------
 * 答案思路：
 * 当我们有了前缀和数组 sum 之后，需要求任意一段子数组 [i,j] 的和
 * 可以直接通过 sum[j] - sum[i - 1] 得出。
 * 现在 通过sum可以求得所有的子数组和的情况
 * 那么使得sum[j]最大，sum[i-1]最小，即为答案（sum[j]为正，sum[i-1]为负数）
 * 如果最大的前缀和数组为负数，则答案应该为Math.abs(前缀和最小)
 * 如果最小的前缀和数组为正数，则答案应该为前缀和最大
 * */
public class Solution1749 {
    public int maxAbsoluteSum(int[] nums) {
        int sum[] = new int[nums.length];
        for (int i = 0; i < sum.length; i++) {
            if (i == 0) sum[i] = nums[i];
            else {
                sum[i] = sum[i - 1] + nums[i];
            }
        }
        Arrays.sort(sum);
        if (sum[0] > 0) return sum[sum.length - 1];
        if (sum[sum.length - 1] < 0) return Math.abs(sum[0]);
        return sum[sum.length - 1] - sum[0];
    }
}
